{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Palindrome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #hash-table #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #哈希表 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestPalindrome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最长回文串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个包含大写字母和小写字母的字符串<meta charset=\"UTF-8\" />&nbsp;<code>s</code>&nbsp;，返回&nbsp;<em>通过这些字母构造成的 <strong>最长的回文串</strong></em>&nbsp;。</p>\n",
    "\n",
    "<p>在构造过程中，请注意 <strong>区分大小写</strong> 。比如&nbsp;<code>\"Aa\"</code>&nbsp;不能当做一个回文字符串。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1: </strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong>s = \"abccccdd\"\n",
    "<strong>输出:</strong>7\n",
    "<strong>解释:</strong>\n",
    "我们可以构造的最长的回文串是\"dccaccd\", 它的长度是 7。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong>s = \"a\"\n",
    "<strong>输出:</strong>1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong>s = \"aaaaaccc\"\n",
    "<strong>输出:</strong>7</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 2000</code></li>\n",
    "\t<li><code>s</code>&nbsp;只由小写 <strong>和/或</strong> 大写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-palindrome](https://leetcode.cn/problems/longest-palindrome/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-palindrome](https://leetcode.cn/problems/longest-palindrome/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abccccdd\"', '\"a\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> int:\n",
    "        if len(set(s)) == 1 or s[::-1] == s: return len(s)\n",
    "        result, odd_flag = len(s), False\n",
    "        count_list = sorted([s.count(each_s) for each_s in set(s)])\n",
    "        # note that single word need to be added once, and which is not together with the odd numbers.\n",
    "        if 1 in count_list:\n",
    "            start = count_list.count(1)\n",
    "            result = result - count_list.count(1) + 1\n",
    "            odd_flag = True\n",
    "        else:\n",
    "            start = 0\n",
    "        for i in range(start, len(count_list)):\n",
    "            if count_list[i] % 2 != 0 and not odd_flag:\n",
    "                odd_flag = True\n",
    "            elif count_list[i] % 2 != 0:\n",
    "                result = result - (count_list[i] % 2) \n",
    "        return result\n",
    "    \n",
    "        # have error?\n",
    "        # ans = 0\n",
    "        # for v in collections.Counter(s).values():\n",
    "        #     ans += v // 2 * 2\n",
    "        #     if ans % 2 == 0 and v % 2 == 1:\n",
    "        #         ans += 1\n",
    "        # return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        a=[]\n",
    "        b=0\n",
    "        d=0\n",
    "        for i in set(s):\n",
    "            a.append(s.count(i))\n",
    "        for i in a:\n",
    "            b+=i//2\n",
    "            if i%2==1:\n",
    "                d=1\n",
    "        b=b*2\n",
    "        return b+d\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        ans = odd = 0\n",
    "        cnt = collections.Counter(s)\n",
    "        for c in cnt:\n",
    "            ans += cnt[c]\n",
    "            if cnt[c]%2 == 1:\n",
    "                ans -= 1\n",
    "                odd += 1\n",
    "        return ans + (odd > 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        from collections import Counter\n",
    "        odds = sum(v & 1 for v in Counter(s).values())\n",
    "        return len(s) - odds + bool(odds)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> int:\n",
    "        from collections import Counter\n",
    "        res=0\n",
    "        m=Counter(s)\n",
    "        for ss in m:\n",
    "            if m[ss]//2 >0:\n",
    "                if m[ss]%2==0:\n",
    "                    res+=m[ss]\n",
    "                else:\n",
    "                    res+=m[ss]-1\n",
    "        if res<len(s):\n",
    "            res+=1\n",
    "        return res\n",
    "                \n",
    "            \n",
    "\n",
    "            \n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        dic = {}; sum_ = 0; flag = 0\n",
    "        for i in s:\n",
    "            if i in dic: dic[i] += 1\n",
    "            else: dic[i] = 1\n",
    "        for key in dic:\n",
    "            if dic[key]%2 == 0: sum_ += dic[key]\n",
    "            else:\n",
    "                sum_ += dic[key] - 1\n",
    "                flag = 1\n",
    "        sum_ += flag\n",
    "        return sum_\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> int:\n",
    "        result = 0\n",
    "        se = set()\n",
    "        for i in s:\n",
    "            if i in se:\n",
    "                se.remove(i)\n",
    "                result += 2\n",
    "            else:\n",
    "                se.add(i)\n",
    "        if se:\n",
    "            return result + 1\n",
    "        return result\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def longestPalindrome(self, s: str) -> int:\r\n",
    "        dic = {}\r\n",
    "        for char in s:\r\n",
    "            dic[char] = dic.get(char,0)+1\r\n",
    "        res,odd = 0,0\r\n",
    "        for v in dic.values():\r\n",
    "            res += v//2 * 2\r\n",
    "        if res < len(s):\r\n",
    "            res += 1\r\n",
    "        return res\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> int:\n",
    "        # 分为奇数个和偶数个；每次看半边\n",
    "        count_map = Counter(s)\n",
    "        result = 0\n",
    "        flag = 0\n",
    "        for i in count_map.keys():\n",
    "            if count_map[i] % 2 == 1:\n",
    "                # result += count_map[i] // 2\n",
    "                flag += 1\n",
    "            result += count_map[i] // 2\n",
    "\n",
    "        if flag > 0:\n",
    "            return result * 2 + 1\n",
    "        else:\n",
    "            return result * 2        \n",
    "\n",
    "\n",
    "    \n",
    "\n",
    "\n",
    "  \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> int:\n",
    "        hash_map = {}\n",
    "        for i in s:\n",
    "            hash_map.setdefault(i, 0)\n",
    "            hash_map[i] += 1\n",
    "        res = []\n",
    "        mid_flag = False\n",
    "        for i, v in hash_map.items():\n",
    "            while v > 0:\n",
    "                if v >= 2:\n",
    "                    res.insert(0, i)\n",
    "                    res.append(i)\n",
    "                    v -= 2\n",
    "                elif not mid_flag and v == 1:\n",
    "                    mid = len(res) // 2\n",
    "                    mid_flag = True\n",
    "                    res.insert(mid, i)\n",
    "                    v -= 1\n",
    "                else:\n",
    "                    break\n",
    "        return len(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> int:\n",
    "        res = 0\n",
    "        from collections import defaultdict\n",
    "        dicts = defaultdict(int)\n",
    "        single = False\n",
    "        for st in s:\n",
    "            dicts[st] += 1\n",
    "        for key in dicts:\n",
    "            if dicts[key] % 2 == 0:\n",
    "                res += dicts[key]\n",
    "            else:\n",
    "                res += 2 * (dicts[key] // 2)\n",
    "                single = True\n",
    "        return res if not single else res + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> int:\n",
    "        sum = 0\n",
    "        for times in Counter(s).values():\n",
    "            if times >= 2:\n",
    "                sum += times // 2\n",
    "        if 2 * sum != len(s):\n",
    "            return 2 * sum +1\n",
    "        return 2 * sum\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> int:\n",
    "        n = 0\n",
    "        for a in set(s):\n",
    "            if s.count(a)%2 != 0:\n",
    "                n += s.count(a) - 1\n",
    "            else:\n",
    "                n += s.count(a)\n",
    "        if len(s) > n:\n",
    "            n += 1\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> int:\n",
    "        offset = ord('A')\n",
    "        mp = [0] * (ord('z') - offset + 1)\n",
    "        for item in s:\n",
    "            mp[ord(item) - offset] += 1\n",
    "\n",
    "        ans = 0\n",
    "        has_odd = False\n",
    "        for item in mp:\n",
    "            if item % 2 == 0:\n",
    "                ans += item\n",
    "            else:\n",
    "                ans += item - 1\n",
    "                has_odd = True\n",
    "\n",
    "        ans = ans + (1 if has_odd else 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> int:\n",
    "        s1 = list(s)\n",
    "        countLower = [0 for i in range(26)]\n",
    "        countUpper = [0 for i in range(26)]\n",
    "        \n",
    "        for c in s1 :\n",
    "            if c.isupper() :\n",
    "                countUpper[ord(c)-ord('A')] += 1\n",
    "            else :\n",
    "                countLower[ord(c)-ord('a')] += 1\n",
    "               \n",
    "        isodd = False\n",
    "        maxNum = 0\n",
    "        for i in countLower :\n",
    "            if i % 2 == 1 :\n",
    "                isodd = True\n",
    "                maxNum += i -1\n",
    "            else :\n",
    "                maxNum += i\n",
    "            print(i, maxNum)\n",
    "                \n",
    "        for i in countUpper :\n",
    "            if i % 2 == 1 :\n",
    "                isodd = True\n",
    "                maxNum += i -1\n",
    "            else :\n",
    "                maxNum += i\n",
    "        \n",
    "        if isodd :\n",
    "            maxNum += 1\n",
    "        \n",
    "        return maxNum\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> int:\n",
    "        ans=0\n",
    "        count=collections.Counter(s)\n",
    "        for v in count.values():\n",
    "            ans += v//2 *2\n",
    "            if ans %2 ==0 and v % 2==1:\n",
    "                ans +=1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> int:\n",
    "        tmp=[0]*52\n",
    "        f,m=0,0\n",
    "        for i in s:\n",
    "            tmp[ord(i)-(72 if i >'Z' else 65)]+=1\n",
    "        for i in tmp:\n",
    "            if not f&1:f+=i\n",
    "            else:\n",
    "                f+=i-1\n",
    "                m+=1\n",
    "        return f+(1 if m>0 else 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> int:\n",
    "\n",
    "        nums_map= {}\n",
    "\n",
    "        for once_char in s:\n",
    "            nums_map.setdefault(once_char,0)\n",
    "            nums_map[once_char]+=1\n",
    "\n",
    "        ans = 0\n",
    "        for once_char in nums_map:\n",
    "\n",
    "            ans += nums_map[once_char]//2*2\n",
    "            if ans%2==0 and nums_map[once_char]%2==1:\n",
    "                ans+=1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> int:\n",
    "        char_dic = {}\n",
    "        for c in s:\n",
    "            if c not in char_dic.keys():\n",
    "                char_dic[c] = 0\n",
    "            char_dic[c] += 1\n",
    "        ret = 0\n",
    "        flag = False\n",
    "        for key in char_dic.keys():\n",
    "            if flag == False and char_dic[key]%2 == 1:\n",
    "                flag = True\n",
    "            ret += char_dic[key] if char_dic[key]%2 == 0 else char_dic[key] - 1\n",
    "        if flag:\n",
    "            ret += 1\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def proc_even(evenDict):\n",
    "    half=''\n",
    "    for k in sorted(evenDict.keys()):\n",
    "        half+=k*int(evenDict[k]/2)\n",
    "    return half+half[::-1]\n",
    "\n",
    "\n",
    "def proc_odd___Out_is_list_of_tuple(oddDict):\n",
    "    midStr_AND_evenDictToAdd___key_is_len={}\n",
    "    for keepThis in oddDict.keys():\n",
    "        od=oddDict.copy()\n",
    "        del od[keepThis]\n",
    "        evenToAdd={}\n",
    "        for k,v in od.items():\n",
    "            if v-1>0:\n",
    "                evenToAdd[k]=v-1\n",
    "        del od\n",
    "        totLen=oddDict[keepThis]+sum(evenToAdd.values())\n",
    "        mid=keepThis*oddDict[keepThis]\n",
    "        try:\n",
    "            midStr_AND_evenDictToAdd___key_is_len[totLen].append((mid,evenToAdd))\n",
    "        except:\n",
    "            midStr_AND_evenDictToAdd___key_is_len[totLen]=[(mid,evenToAdd)]\n",
    "    return midStr_AND_evenDictToAdd___key_is_len[max(midStr_AND_evenDictToAdd___key_is_len.keys())]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "def get_longest_palindrome_with_smallest_lexicographic_order(s) -> str:\n",
    "    if len(s)==1:\n",
    "        return s\n",
    "################################################################################################\n",
    "    d={}\n",
    "    for ss in s:\n",
    "        try:\n",
    "            d[ss]+=1\n",
    "        except:\n",
    "            d[ss]=1\n",
    "\n",
    "    if max(d.values())==1:\n",
    "        return min(d.keys())\n",
    "################################################################################################\n",
    "################################################################################################\n",
    "    evenDict={}\n",
    "    oddDict={}\n",
    "    for k in d.keys():\n",
    "        if d[k]%2==0:\n",
    "            evenDict[k]=d[k]\n",
    "        else:\n",
    "            oddDict[k]=d[k]\n",
    "\n",
    "\n",
    "\n",
    "    if oddDict=={}:\n",
    "        return proc_even(evenDict)\n",
    "    tmpd={}\n",
    "    for t in proc_odd___Out_is_list_of_tuple(oddDict):\n",
    "        mid=t[0]\n",
    "        evenToAdd=t[1]\n",
    "        ed=evenDict.copy()\n",
    "        for k,v in evenToAdd.items():\n",
    "            try:\n",
    "                ed[k]+=v\n",
    "            except:\n",
    "                ed[k]=v\n",
    "        tmpd[mid]=''.join(sorted(''.join([k*int(v/2) for k,v in ed.items()])))\n",
    "        del ed\n",
    "    d={head+mid:head for mid,head in tmpd.items()}\n",
    "    head_AND_mid=min(d.keys())\n",
    "    tail=d[head_AND_mid][::-1]\n",
    "    return head_AND_mid+tail\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> int:\n",
    "        return len(get_longest_palindrome_with_smallest_lexicographic_order(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from curses.ascii import isupper\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> int:\n",
    "        hs = [0] * 52\n",
    "        for x in s:\n",
    "            if isupper(x):\n",
    "                hs[ord(x) - ord('A') + 26] += 1\n",
    "            else:\n",
    "                hs[ord(x) - ord('a')] += 1\n",
    "            \n",
    "        max_odd = False\n",
    "        res = 0\n",
    "        for i in hs:\n",
    "            if i & 1:\n",
    "                max_odd = True\n",
    "                res += i - 1\n",
    "            elif not (i & 1):\n",
    "                res += i\n",
    "        \n",
    "        return res + max_odd "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        cnt = collections.Counter(s)\n",
    "        for v in cnt.values():\n",
    "            ans += v//2*2\n",
    "            if ans % 2 == 0 and v%2==1:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> int:\n",
    "        rec = {}\n",
    "        ans = 0\n",
    "        for c in s:\n",
    "            if c not in rec:\n",
    "                rec[c]=1\n",
    "            else:\n",
    "                rec[c]+=1\n",
    "        for val in rec.values():\n",
    "            if val%2==1:\n",
    "                ans+=1\n",
    "        return len(s)-ans+1 if ans!=0 else len(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> int:\n",
    "        D = {}\n",
    "        Max = 0\n",
    "        for i in s:\n",
    "            if i not in D: D[i]=0\n",
    "            D[i] += 1\n",
    "        Res = 0\n",
    "        Flag = 0\n",
    "        for key in D:\n",
    "            Res += D[key]\n",
    "            if D[key]%2!=0: \n",
    "                Res -= 1\n",
    "                Flag = 1\n",
    "\n",
    "        return Res + Flag\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
